package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-25 16:58
 */
public class BB198打家劫舍I {

    public static void main(String[] args) {
        int[] nums = {1,2,3,1,5};
        System.out.println(rob(nums));
    }


    /**
     * F(n) = F(n-2)+n or F(n-3)+ max(n,n-1)
     *
     * F(n) >F(n-2) 这个是必然的
     *
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        dp[2] = Math.max(nums[0], nums[1]);
        for (int i = 3; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 3] + nums[i - 2]);
        }
        return dp[nums.length];
    }


    /**
     * 2
     * f(n) = f(n-1) or f(n-2)+n-1
     *
     * @param nums
     * @return
     */
    public static int rob2(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int one = nums[0];
        int two = Math.max(nums[0], nums[1]);
        for (int i = 3; i <= nums.length; i++) {
            int next = Math.max(two, one + nums[i - 1]);
            one = two;
            two = next;
        }
        return two;
    }
}
